package Mul;

// 剑指 Offer 66. 构建乘积数组
public class Mul {
    
}
//使用了两个数组保存前后的乘积
//实际上可以通过边计算边保存到ans数组中省掉空间的使用
class Solution_Five009 {
    public int[] constructArr(int[] a) {
        int[] ans = new int[a.length];
        if(a.length==0) return ans;
        int[] from0 = new int[a.length];
        int[] toend = new int[a.length];
        int tmp =1;
        for(int i=0;i<a.length;i++){
            from0[i]= tmp = tmp*a[i];
        }
        tmp = 1;
        for(int i=a.length-1;i>=0;i--){
            toend[i] = tmp = a[i]*tmp;
        }
        ans[0]= toend[1];
        ans[a.length-1]= from0[a.length-2];
        for(int i=1;i<a.length-1;i++){
            ans[i] = from0[i-1]*toend[i+1];
        }
        return ans;
    }
}

//优化空间版
class Solution{
    public int[] constructArr(int[] a){
        int ans[] = new int[a.length];
        if(a.length==0) return ans;
        ans[0]=1;
        for(int i=1;i<a.length;i++){
            ans[i] = a[i-1]*ans[i-1];
        }
        int tmp = a[a.length-1];
        for(int i=a.length-2;i>=0;i--){
            ans[i]*=tmp;
            tmp*=a[i];
        }

        return ans;
    }
}
